Subject: Can't you make your mailer attach appropriate subject, Ariel?

From: [email-masked] (Ariel Orda)
Date: Thu, 8 May 1997 17:51:25 +0300

Masataka,

  >
  >Can you show me the reference to [Go96] again?
  >
Oops, I now see that in my first note I referenced it as [GuOr] - sorry
for that. Here are the references:

[GuOr] Roch Guerin and Ariel Orda, "QoS-based routing in Networks with
       Inaccurate Information: Theory and Algorithms". IBM Report,
       July 96. (Available through http://www.watson.ibm.com:8080/.)

[GO2] Roch Guerin and Ariel Orda, "QoS-based routing in Networks with
       Inaccurate Information: Theory and Algorithms". In Proceedings
       of Infocom'97.

  >
  >>   >It's not uncertainity, at all.
  >
  >>   >Aggregation naturally brings in inaccuracy, which is unavoidable
  >>   >but NOT a problem here.
  >
  >> Well, when the information is "inaccurate", the path selection process fac
es
  >> "uncertainty".
  >
  >What, do you mean, "uncertainity" is?
  >
We defined it in [GuOr], but it essentially amounts to the fact that
you cannot be sure that the appropriate resources are available, even
when the advertised information states they are.

  >With moderate underestimation of resource, we can "certainly" find
  >a path without cranking back operations.
  >
  >Then, there is a possibility that a certain path can not be found,
  >becasue of underestimated aggregated resource, which is not a
  >problem.
  >
  >Of course, there can be transient uncertainity even if we don't
  >aggregate. But, simple retry can get around it.
  >
Certainly, but in general it is desirable to avoid as much as possible
retries or any other form of crankback. Hence, you would like your
(path selection) algorithm to not only try to pick the "cheapest" path
that meets your constraint, but also do so in a fashion that *minimizes*
the likelihood you'll have to retry (or crankback). Again, see 
[GuOr]/[GO2] for details on this.

  >> namely finding the path
  >> that satisfies the delay constraint with the minimum bandwidth, can be
  >> found as follows, using the standard approach presented in the above 
  >> studies. 
  >
  >Sorry, but, your modification does not work.
  >
  >> (1) Execute the Bellman-Ford algorithm for all (up to M) bandwidth/rate 
  >> values.
  >
  >OK.
  >
  >> (2) In each execution, record the shortest path (w.r.t. the "constant 
  >> delays" metric of each link) for each possible hop count.
  >
  >No. The Bellman-Ford algorithm finds a best path with no more,
  >hop count than, but not necessarily equal to, the current hop
  >limit.
  >
What you say about the BF algorithm is true, but has no bearing on the result.
Actually, even if it had, it would have only required a mild modification
of the BF algorithm to "fix" this. This is somewhat of a digression, but let 
me quickly outline why this is so.

\begin{digression}
Let's consider the case where for each hop count n you need to produce the best
path with *exactly* n hops. It is easy to see that this can be done through a 
modification of the BF algorithm as follows: 

at the n'th iteration of BF, when considering a node i, instead of computing

d_i(n) = min( d_i(n-1), min_k (d_k(n-1) + d_{k,i}) )

as in the standard algorithm, one computes

d_i(n) = min_k (d_k(n-1) + d_{k,i});

in addition, the initialization is:
for the source s: d_s(0) = 0 , d_s(n) = infinity for n>0
for i<>s: d_i(n) = infinity for all n.
\end{digression}

Now, let's come back to the fact that the algorithm described in the previous 
note does not require the above modification to the BF algorithm, i.e.,
it generates the correct path using a standard BF algorithm. For that 
purpose, let's consider the form of the Guaranteed Service [GS96] 
end-to-end delay bound. In the expression for the GS bound, decreasing 
the hop count while keeping all other parameters, i.e., rate/bandwidth and 
propagation delays, constant, results in a lower bound. This is the only thing 
we need for the result to hold (as pointed out, this is applicable to more 
general cost functions that also satisfy similar requirements). Let's clarify 
things further through an explicit example:

For a path p with n hops and end-to-end propagation delay d, and
for (consumed) bandwidth b, denote by D(p,b)=D(n,d,b) the end to end delay
bound corresponding to [GS96]. D(n,d,b) increases with n and d, and decreases
with b.
Suppose that the optimal path (according to the above criterion) is p1, with n1
hops, consumed bandwidth b1 and end-to-end propagation delays d1. Therefore,
D(p1,b1) = D(n1,d1,b1) <= D, where D is the end to end delay constraint.
Also, denote by B1 the maximal available bandwidth on p1's bottleneck link. 
We'll now show that the algorithm (specified in my previous note) identifies 
a path which is at least as good.

Consider the iteration at which we run the BF algorithm for links with
bottleneck bandwidth of at least B1. Let p2 be the path identified at the
n1-th step of that execution of BF, and denote by n2, d2 and B2 its 
corresponding number of hops, end to end propagation delay and bottleneck 
bandwidth. By the BF we have:
(1) n2 =< n1,
(2) d2 =< d1,
and since it was executed at the the iteration corresponding to "B1-links":
(3) B2 >= B1.
The algorithm then chooses the minimal bandwidth, say b2, that still satisfies
the end-to-end bound D on p2. We will show that b2<= b1, as required.
Consider the following:

(A) Since b1<= B1 and B1<= B2 (by (3)), it follows that b1 <= B2.
(B) D(p2,b1) = D(n2,d2,b1) <= D(n1,d2,b1) <= D(n1,d1,b1) = D(p1,b1) <= D,
where the first inequality is due to (1) and the second is due to (2).

By (A), b1 is a permissible bandwidth value on p2, and by (B), it satisfies
on p2 the end to end delay constraint. Since b2 is the minimal such value, we
have that b2 <= b1, i.e., the algorithm identifies a path which is at least
as good as p1. This completes the proof.

Ariel

----- End Included Message -----

---

From: Masataka Ohta <[email-masked]>
Date: Fri, 9 May 97 9:51:40 JST

Ariel;

>        July 96. (Available through http://www.watson.ibm.com:8080/.)

Thank you. I may look at it if I have time.

> when the advertised information states they are.

Then, inaccuracy does not mean uncertainity.

Inaccuracy means uncertainity only when you aggregate inappropriately.

> retries or any other form of crankback.

Sure. So, just have pessimistic aggregattion.

And, you miss my last point. That is, transient uncertainity is
unavoidable as long as there is packet transmission delay or
packet loss possibility, both of which is quite common in the
real networks, which is totally unrelated to aggregation.

> Hence, you would like your
> the likelihood you'll have to retry (or crankback).

That's a requirement with self contradiction.

If we choose "cheapest", there is practically no room to "*minimizes*"
something else.

An unrealistic exception could be when "cheapest" means hop count or
some integral metric and the diameter is less than, say, 5. But, it
is just impractical.

> Again, see 

Anyway, with pessimistic aggregation, the likelifood of failure is
already minimal only bounded by transient inconsistency. So, don't
bother to do otherwise.

> What you say about the BF algorithm is true,

What I say about Qingming's result is true.

> but has no bearing on the result.

Wrong, becasue the complexity is not the same.

> of the BF algorithm to "fix" this.

I know.

The problem is that, now, you must compute modified-BF "for all the hop
count" in addition to "for all the bandwidth".

Thus, the complexity is now different.

It is, still, theoretically interesting slightly that the result is still
polynominal.

If you are interested in writing a research paper on it, feel free to
do so, as long as I am included as a co-author.

> propagation delays, constant, results in a lower bound.

As I repeatedly said, Qingming's algorithm is fine to find the
existence of a path. But, it is no good to find the path.

The problem is that, after we find a path we should decrease the
required bandwidth, which affect the queueing delay, which then
affect the end-to-end delay in non-uniform fashion.

That is, your assumption that "keeping all other paramters" is wrong.

							Masataka Ohta